package com.lry.basic.algorithm.search;

import java.util.Arrays;

class Radius {

    public static void main(String[] args) {
        System.out.println(findRadius(new int[]{282475249,622650073,984943658,144108930,470211272,101027544,457850878,458777923},
                new int[]{823564440,115438165,784484492,74243042,114807987,137522503,441282327,16531729,823378840,143542612}));
    }

    public static int findRadius(int[] houses, int[] heaters) {
        
        Arrays.sort(heaters);

        for (int heater : heaters) {
            System.out.print(heater+" ");
        }
        System.out.println();
        int ans = 0;

        for(int house:houses){
            int s = search(heaters,house);
            if(s>ans){
                ans = s;
            }
        }
        return ans;
    }

    //找出离房子最近的热水器的距离, 3 5 7  , 4
    private static int search(int[] heaters,int house){
        if(heaters[0]>=house){
            return heaters[0]-house;
        }
        if(house>=heaters[heaters.length-1]){
            return house-heaters[heaters.length-1];
        }

        //找到数组中第一个大于house的数字
        int left = 0;
        int right = heaters.length-1;

        while(left<right){
            int mid = left + (right-left)/2;

            if(house>heaters[mid]){
                left = mid +1;
            }else if(house<heaters[mid]){
                right = mid;
            }else{
                return 0;
            }
        }
        System.out.println("left="+left);
        return Math.min(Math.abs(house-heaters[left]), left-1>=0?Math.abs(house-heaters[left-1]):Integer.MAX_VALUE);
    }

}